// -*- coding: utf-8 -*-
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-26 23:44
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan.threeLeafTrains;

import java.util.Arrays;

public class DeleteAndEarn {
    /**
     * 删除并获得点数
     * 动态规划
     */
    public int deleteAndEarn(int[] nums) {
        int n = nums.length, N = 1_000_9, max = 0;
        int[] a = new int[N];
        Arrays.fill(a, 0);
        for (int num : nums) {
            a[num]++;
            max = Math.max(max, num);
        }
        int[][] f = new int[max + 1][2];
        for (int i = 1; i <= max; i++) {
            // 当前没选
            f[i][1] = f[i - 1][0] + i * a[i];
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
        }
        return Math.max(f[max][0],f[max][1]);
    }
}
